// 状态转移方程
/*
    DP[i] = max(DP[i-2] + nums[i], DP[i-1]) ，选择取或者不取i元素
    DP[i] 表示数组num[0...i]的最大值，
*/

#define MAX(x, y) ((x) > (y) ? (x) : (y))
int rob(int *nums, int numsSize)
{
    int i;
    int *DP = (int *)malloc(sizeof(int) * numsSize);
    if (numsSize == 0)
    {
        return 0;
    }
    if (numsSize == 1)
    {
        return nums[0];
    }
    if (numsSize == 2)
    {
        return MAX(nums[0], nums[1]);
    }

    DP[0] = nums[0];
    DP[1] = MAX(nums[0], nums[1]);
    for (i = 2; i < numsSize; i++)
    {
        // 选择取或者不取
        DP[i] = MAX(DP[i - 2] + nums[i], DP[i - 1]);
    }
    return DP[numsSize - 1];
}
